﻿// 0812train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。
 请从 nums 中找出并返回总和为 target 的元素组合的个数。
 数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
 */

int solve01(vector<int>&nums, int target)
{
	int dp_size = target + 1;
	vector<int>dynamic_vec(dp_size, 0);
	dynamic_vec[0] = 1;

	for (int prev_sum=0; prev_sum<=target; prev_sum++)
	{
		for (auto&num:nums)
		{
			int curr_sum = prev_sum + num;
			int sum_count = dynamic_vec[prev_sum];
			if (curr_sum<=target)
			{
				dynamic_vec[curr_sum] += sum_count;
			}
		}
	}
	int result = 0;
	for (int sum=0; sum<=target; sum++)
	{
		result = max(result, sum);
	}
	return dynamic_vec[result];
	//solve01
}

//防溢出版本
int solve11(vector<int>& nums, int target)
{
	int dp_size = target + 1;
	vector<long long>dynamic_vec(dp_size, 0);
	dynamic_vec[0] = 1;

	for (int prev_sum = 0; prev_sum <= target; prev_sum++)
	{
		for (auto& num : nums)
		{
			int curr_sum = prev_sum + num;
			int sum_count = dynamic_vec[prev_sum];
			if (curr_sum <= target)
			{
				if (sum_count>=INT_MAX)
				{
					dynamic_vec[curr_sum] = INT_MAX;
					continue;
				}
				dynamic_vec[curr_sum] += sum_count;
			}
		}
	}
	int result = 0;
	for (int sum = 0; sum <= target; sum++)
	{
		result = max(result, sum);
	}
	return dynamic_vec[result];
	//solve01
}


/*
 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
 */
int solve02(int amount, vector<int>& coins)
{
	int dp_size = amount + 1;
	vector<long long>dynamic_vec(dp_size, 0);
	dynamic_vec[0] = 1;

	for (auto&num: coins)
	{
		for (int prev_sum=0; prev_sum<dp_size; prev_sum++)
		{
			int curr_sum = num + prev_sum;
			int sum_count = dynamic_vec[prev_sum];

			if (curr_sum<=amount)
			{
				if (sum_count>=INT_MAX)
				{
					dynamic_vec[curr_sum] = INT_MAX;
					continue;
				}
				dynamic_vec[curr_sum] += sum_count;
			}

		}
	}


	return dynamic_vec[amount];
	//solve02-----
}

int main()
{
	{
		//amount = 5, coins = [1, 2, 5]
		int amount = 5;
		vector<int>coins = { 1,2,5 };
		cout << solve02(amount, coins);
		return 0;
	}
	//nums = [1,2,3], target = 4
	vector<int>nums = { 1,2,3 };
	int target = 4;
	cout << solve01(nums, target);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
